package com.my.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Created by ZhongGang
 * at 2018/10/8 17:02
 * <p>
 * 插入排序
 * 依次遍历数组的前N个元素，保证前N个元素为有序的，遍历至数组最后一个元素时，数组为有序状态
 * <p>
 * 复杂度 N的平方
 */
public class InsertionSorter<T extends Comparable<T>> implements Sortable<T> {
    private static final Logger LOGGER = LoggerFactory.getLogger(InsertionSorter.class);

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }

        int length = elements.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0; j--) {
                if (elements[j - 1].compareTo(elements[j]) > 0) {
                    T tmp = elements[j];
                    elements[j] = elements[j - 1];
                    elements[j - 1] = tmp;
                }
                LOGGER.info("i: {}, j: {}, elements: {}", i, j, elements);
            }
        }

        return elements;
    }
}
